import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
def solve():
n = int(input())
a = list(map(int, input().split()))
m = int(input())
a.sort()
s = sum(a)
for i in range(m):
attack, defence = map(int, input().split())
begin, end = 0, n
while True:
mid = (begin + end) // 2
mm = a[mid]
if end - begin < 2:
break
if mm <= attack:
begin = mid
else:
end = mid
ans = max(defence - (s - a[end]), 0) if end != n else int(10**20)
ans = min(ans, max(attack - a[begin], 0) + max(defence - (s - a[begin]), 0))
sys.stdout.write(f'{ans}\n')
if __name__ == '__main__':
solve()
#include<bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define endl "\n"
#define space " "
#define printArray(a, n) for(int i=0;i<n;i++) cout<<a[i]<<space; cout<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,int> pci;
typedef map<int,int> mii;
typedef vector<int> vi;
const int MOD = 1e9 + 7;
//---------------------------------------------------------------------------------------------------//
static bool cmp(pair<int,int> a, pair<int,int> b)
{
if (a==b)
{
return a.second<b.second;
}
return a.first<b.first;
}int lowerBound(int arr[], int n, int x)
{
int low=0, high=n-1;
int mid=(low+high)/2;
while(high-low>1)
{
mid=(high+low)/2;
if (arr[mid]<x)
{
low=mid+1;
}
else //
{
high=mid;
}
}
if (arr[low]>=x)
{
return low;
}
else if (arr[high]>=x)
{
return high;
}
else
{
return -1;
}
}
void solve()
{
int n;
cin>>n;
int arr[n];
int sumArr=0;
for(int i=0;i<n;i++)
{
cin>>arr[i];
sumArr+=arr[i];
}
int m;
cin>>m;
pii dragon[m];
for(int i=0;i<m;i++)
{
cin>>dragon[i].first;
cin>>dragon[i].second;
}
sort(arr, arr+n);
int sum=sumArr;
for(int i=0;i<m;i++)
{
sumArr=sum;
int k=lowerBound(arr, n, dragon[i].first);
if (k==-1)
{
//not found
int value=arr[n-1];
sumArr=sumArr-value;
int answer=dragon[i].first-value;
// cout<<sumArr<<"HKJ "<<endl;
if (sumArr<dragon[i].second)
{
answer+=dragon[i].second-sumArr;
}
cout<<answer<<""<<endl;
}
else
{
int value = arr[k];
int answer=0;
// if (value<dragon[i].first)
// {
// answer+=dragon[i].first-value;
// }
sumArr=sumArr-value;
if (sumArr<dragon[i].second)
{
answer+=dragon[i].second-sumArr;
}
sumArr=sum;
int answer2=LONG_LONG_MAX;
if(k>0)
{
// value = *(--k);
value=arr[k-1];
answer2=0;
if (value<dragon[i].first)
{
answer2+=dragon[i].first-value;
}
sumArr=sumArr-value;
if (sumArr<dragon[i].second)
{
answer2+=dragon[i].second-sumArr;
}
}
cout<<min(answer, answer2)<<endl;
}
}
}
int32_t main()
{
fastIO;
int t=1;
while(t--)
{
solve();
}
return 0;
}Lexical Sorting Reloaded | 1514A - Perfectly Imperfect Array |
580A- Kefa and First Steps | 1472B- Fair Division |
996A - Hit the Lottery | MSNSADM1 Football |
MATCHES Playing with Matches | HRDSEQ Hard Sequence |
DRCHEF Doctor Chef | 559. Maximum Depth of N-ary Tree |
821. Shortest Distance to a Character | 1441. Build an Array With Stack Operations |
1356. Sort Integers by The Number of 1 Bits | 922. Sort Array By Parity II |
344. Reverse String | 1047. Remove All Adjacent Duplicates In String |
977. Squares of a Sorted Array | 852. Peak Index in a Mountain Array |
461. Hamming Distance | 1748. Sum of Unique Elements |
897. Increasing Order Search Tree | 905. Sort Array By Parity |
1351. Count Negative Numbers in a Sorted Matrix | 617. Merge Two Binary Trees |
1450. Number of Students Doing Homework at a Given Time | 700. Search in a Binary Search Tree |
590. N-ary Tree Postorder Traversal | 589. N-ary Tree Preorder Traversal |
1299. Replace Elements with Greatest Element on Right Side | 1768. Merge Strings Alternately |